using System.Collections.Generic;
using System;

namespace Mono.Boost.Graph
{
    public class Flows
    {
        public static uint edmonds_karp<GraphType, FlowType, MaxFlowType>(GraphType g, FlowType flow, MaxFlowType maxFlow, uint source, uint destination)
            where GraphType : IGraph
            where FlowType : IDictionary<uint, uint>
            where MaxFlowType : IDictionary<uint, uint>
        {
            uint sumFlow = 0;
            foreach(EdgeFullInfo ei in g.edges)
                if(!flow.ContainsKey(ei.id))
                    flow.Add(ei.id,0);

            //Edge leading from previous vertex on a path from source
            StaticPropertyMap<uint> prev = new StaticPropertyMap<uint>(g.highestVertexId + 1);

            //Queue for DFS
            Queue<uint> q = new Queue<uint>();

            //TODO: Should we fill flow with zeros here?

            while (true)
            {
                prev.Clear();

                prev.Add(source, uint.MaxValue - 1);   //not a real ID, but not infty, to make difference from unchecked vertices
                q.Enqueue(source);

                //BFS
                while (q.Count != 0)
                {
                    uint now = q.Dequeue();
                    foreach (EdgeInfo ei in g.outgoing(now))
                        if (flow[ei.id] < maxFlow[ei.id] && !prev.ContainsKey(ei.v))
                        {
                            prev.Add(ei.v, ei.id);
                            q.Enqueue(ei.v);
                        }
                    foreach (EdgeInfo ei in g.incoming(now))
                        if (flow[ei.id] > 0 && !prev.ContainsKey(ei.v))
                        {
                            prev[ei.v] = ei.id;
                            q.Enqueue(ei.v);
                        }
                }

                if (!prev.ContainsKey(destination))
                    break;  //No path from source to destination in residual net

                sumFlow += augument(g, flow, maxFlow, prev, source, destination);
            }
            //return value of maximal flow
            return sumFlow;
        }
        public static uint augument<GT, FT, MFT, PT>(GT g, FT flow, MFT maxFlow, PT prev, uint source, uint destination)
            where GT : IGraph
            where FT : IDictionary<uint, uint>
            where MFT : IDictionary<uint, uint>
            where PT : IDictionary<uint, uint>
        {
            uint act = destination;

            //calculate width of augumenting path
            uint width = ~0U;
            while (act != source)
            {
                uint eid = prev[act];
                EdgeFullInfo e = new EdgeFullInfo(g.edge_source(eid), g.edge_destination(eid), eid);
                if (act == e.to)
                {
                    width = System.Math.Min(width, maxFlow[e.id] - flow[e.id]);
                    act = e.from;
                }
                else
                {
                    width = System.Math.Min(width, flow[e.id]);
                    act = e.to;
                }
            }

            //augument path
            act = destination;
            while (act != source)
            {
                uint eid = prev[act];
                EdgeFullInfo e = new EdgeFullInfo(g.edge_source(eid), g.edge_destination(eid), eid);
                if (act == e.to)
                {
                    flow[e.id] = flow[e.id] + width;
                    act = e.from;
                }
                else
                {
                    flow[e.id] = flow[e.id] - width;
                    act = e.to;
                }
            }
            return width;
        }
    }
}

